/**
 * 二分查找
 * 查找n在arr中的位置，如果找不到指定的元素，将返回一个最合适的位置：arr[i]>n,arr[i-1]<n
 * arr必须为升序的数组
 */
class Bisection {
    constructor() {}

    findN(arr, n) {
        arr.sort((a, b) => a - b);

        // 极限情况

        // a[0] > n
        if (n < arr[0]) {
            console.log(`${JSON.stringify(arr)}, find ${n}, result: ${-1}`);
            return -1;
        }

        // a[max] <n
        if (n > arr[arr.length - 1]) {
            console.log(
                `${JSON.stringify(arr)}, find ${n}, result: ${arr.length}`
            );
            return arr.length;
        }

        let startIndex = 0;
        let endIndex = arr.length - 1;
        let findFlag = true;

        while (startIndex < endIndex) {
            let index = Math.ceil((startIndex + endIndex) / 2);
            let ele = arr[index];

            if (ele === n) {
                startIndex = index;
                endIndex = index;
                findFlag = true;
                break;
            } else if (ele > n) {
                endIndex = Math.max(0, index - 1);
                if (arr[endIndex] < n) {
                    startIndex = index;
                    break;
                }
            } else {
                startIndex = Math.min(arr.length - 1, index + 1);
            }
        }

        console.log(`${JSON.stringify(arr)}, find ${n}, result: ${startIndex}`);
        return startIndex;
    }
}

let bisection = new Bisection();
bisection.findN([1, 3, 4], 0);
bisection.findN([1, 3, 4], 2);
bisection.findN([93, 95, 97, 100, 102], 110);
